CS229：01-监督学习&梯度下降法

监督学习

符号定义：

符号	意义
$m$	训练集包含的数据个数
$x$	输入变量/特征（feature）
$y$	输出变量/目标（target）
$(x, y)$	一个训连样本
$(x^{(i)}, y^{(i)})$	第 i 个训练样本

监督学习的主要流程：

线性回归

以预测房价为例，我们的目标是导出一个函数（即假设），根据房子的特征（比如大小、卧室数量等等）来预测房价，那么：

• 输入（特征）：$x_1, x_2, …$（比如大小、卧室数量等等）
• 输出（目标）：$y$（房价）

• 假设：$h(x)=h_{\theta}(x)=\theta_0+\theta_1x_1+\theta_2x_2+…+\theta_nx_n$，用于预测房价，其中$\theta_i$是参数，$n$是特征数量

  为了方便，可以将假设写成：$h(x)=\sum_{i=0}^n\theta_ix_i=\theta^Tx​$

此时，学习函数（Learning Algorithm）的目标就是找到合适的参数$\theta$，使之能够导出『合理』的假设$h(x)$，这里我们将『合理』理解为：$h_\theta(x)$（假设）和$y$（目标）之间的差距最小，也即：

$$\displaystyle \min_{\theta}\frac{1}{2}\sum_{i=1}^m(h_\theta(x)^{(i)}-y_{(i)})^2$$

这里的$\frac{1}{2}$是为了简化之后的计算。

我们定义$\displaystyle J(\theta)=\frac{1}{2}\sum_{i=1}^m(h_\theta(x)^{(i)}-y_{(i)})^2$，那么我们的目标就是去选取合适的$\theta$，以最小化$J(\theta)$。

梯度下降法

搜索算法（梯度下降）

目的：不断改变$\theta$，从而来减少$J(\theta)$。

原理：每次都往下降最快的地方走，从而找到一个局部最优解。

一般会初始化$\vec{\theta}=\vec{0}$，然后每次都沿着梯度方向走，以保证每次都往下降最快的地方走：

$$\displaystyle \theta_i:=\theta_i - \alpha\frac{\partial}{\partial \theta_i}J(\theta)$$

其中，$:=$表示赋值操作，$\alpha$为步长。

对于某个训练样本$(x, y)​$

$$\displaystyle \frac{\partial}{\partial \theta_i}J(\theta) = \frac{\partial}{\partial \theta_i}(\frac{1}{2}(h_\theta(x)-y)^2)$$ $$\displaystyle = 2 \times \frac{1}{2}(h_\theta(x)-y)\frac{\partial}{\partial \theta_i}(h_\theta(x)-y)$$ $$\displaystyle = (h_\theta(x)-y)\frac{\partial}{\partial \theta_i}(\theta_0x_0+…+\theta_nx_n-y)$$ $$\displaystyle =(h_\theta(x)-y) \times x_i$$

那么，

$$\theta_i:=\theta_i - \alpha (h_\theta (x) - y) \times x_i$$

批量梯度下降法（Batch Gradient Descent）

批量梯度下降法，使用的是所有训练样本的平均梯度：

$$\displaystyle \theta_i:=\theta_i - \alpha \frac{1}{m} \sum_{j=1}^m(h_\theta(x^{(j)})-y^{(j)}) \times x_i^{(j)}$$

但每次下降都需要遍历所有样本，效率较低，具体过程可能如下：

随机梯度下降法（Stochastic Gradient Descent）

又称为『增量梯度下降法』

对每个样本$(x_{(j)}, y_{(j)})$进行：

$$\displaystyle \theta_i:=\theta_i - \alpha (h_\theta(x^{(j)})-y^{(j)}) \times x_i^{(j)}$$

直到收敛

这时，每次梯度下降只遍历一个样本，具体过程可能如下：